package alg

import (
	"bytes"
	"fmt"
	"strconv"
)

func QuickPower() {
	p := 16
	result := power2Y(p)
	fmt.Printf("power(2, %d) is: %s \r\n", p, result)

	p1 := 1000
	result1 := power2Y(p1)
	fmt.Printf("power(2, %d) is: %s \r\n", p1, result1)
}

// 快速幂
func power2Y(y int) string {
	slice1 := []int{1}
	slice2 := []int{}
	var temp, quotient, remainder int
	for i := 0; i < y; i++ {
		for j := 0; j < len(slice1); j++ {
			temp = slice1[j] * 2 + quotient
			quotient = temp / 10
			remainder = temp %  10
			slice2 = append(slice2, remainder)
			if j == len(slice1) - 1 && quotient > 0 {
				slice2 = append(slice2, quotient)
				quotient = 0
			}
		}

		slice1 = slice2[:]
		slice2 = slice2[0:0]
	}

	var b bytes.Buffer
	for i := len(slice1) - 1; i >= 0;  i--{
		b.WriteString(strconv.Itoa(slice1[i]))
	}

	return b.String()
}